1 Contenido de la clase
Repaso del árbol de decisiones y del número de hojas [05:05-05:19, 08:35-08:51]
Se retoma el modelo del árbol de decisiones, construido sobre elementos etiquetados (B, C, A, D), con al menos 4 datos de entrada. Se revisan las profundidades de los nodos: el nodo superior tiene profundidad 2, el siguiente 3, y después vienen los niveles 4 y 5 [08:35-08:51]. La idea central es que cada pregunta (comparación) divide los casos posibles en dos, y con H preguntas se distinguen como máximo:
2^H hojas: H=1 → 2, H=2 → 4, H=3 → 8, H=4 → 16 [40:30-40:58]
Por qué no alcanzan "pocas" preguntas [24:01-25:28]
El número de hojas determina cuántos resultados distintos puede distinguir el árbol: "ha sido la 1, tengo 2; ha sido la 2, tengo 4; ha sido la 3, tengo 8". Para ordenar n elementos hay n! permutaciones, así que el árbol necesita al menos n! hojas [24:01-24:19, 25:12-25:16]. Con el ejemplo de n = 3:
- Se necesitan 3! = 6 hojas ("tres factorial", "tres o seis").
- Con 2 preguntas solo se llega a 2² = 4 hojas, que no alcanza.
- Por lo tanto hacen falta al menos 3 comparaciones para ordenar 3 elementos [25:16-25:28].
Límite inferior de la ordenación: log₂(n!) [26:30-29:53]
El argumento es general: para cualquier algoritmo basado en comparaciones, la altura H del árbol en el mejor caso no es del orden de N sino de log₂(n!), y no se puede bajar de ese valor [29:31-29:53]. Se recorren los caminos que van determinando el elemento más pequeño, el segundo y el tercero [26:30-26:46]. [parte no entendida — pasos concretos de la construcción del árbol en la pizarra].
Nuevo problema: encontrar el mínimo [42:51-43:58]
Se transita a un problema más simple: encontrar el mínimo de la lista. La estrategia es comparar desde el inicio, ir quedándose con el más pequeño de cada par y guardar su posición; al final queda el mínimo [43:16-43:58]. El costo es de n−1 comparaciones ("de menos uno") [46:25-46:53].
Método del torneo (eliminación directa) [61:25-64:06]
En vez de recorrer en línea, se organizan las comparaciones como un torneo de eliminación directa: se comparan los elementos de a pares y los ganadores avanzan a la siguiente ronda [61:25-61:56]. El profesor muestra varios emparejamientos de ejemplo: "2 contra 2", "4 contra 4", "6 y 4", "el 8 pasa" [61:25-62:38], y luego "9 y 4", "7 y 7", "9 y 8", "8 y 8", aclarando que los algoritmos no son necesariamente los usuales [63:38-64:06]. [parte no entendida — detalle completo de la demostración].
Segundo y tercer mínimo con la historia del torneo [47:55-48:11, 66:49-66:59]
Para obtener el segundo y tercer mínimo sin recomparar todo desde cero, se usa la historia del torneo: solo pudieron perder contra el ganador aquellos elementos que perdieron directamente contra él, así que basta examinar a los rivales directos del mínimo [47:55-48:11, 66:49-66:59].
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
En esta clase no se dejó ninguna tarea concreta con fecha de entrega. Conviene repasar por cuenta propia:
4 Dudas que podrían examinar
¿Por qué 2 comparaciones no alcanzan para ordenar 3 elementos?
Porque solo distinguen 2² = 4 casos y hay 3! = 6 permutaciones posibles; hacen falta al menos 3 [25:16-25:28].
¿Cómo se relaciona la altura H con el número de hojas?
Con H preguntas hay como máximo 2^H hojas; para ordenar hace falta que 2^H alcance n! [24:01-25:16].
¿Cuánto cuesta encontrar el mínimo en una lista?
n−1 comparaciones, porque basta comparar cada elemento con el mejor actual [46:25-46:53].
¿Qué es el método del torneo?
Comparar los elementos de a pares y hacer avanzar a los ganadores, como en una eliminación directa [61:25-61:56].
¿Cómo se obtiene el segundo y tercer mínimo?
Revisando solo a los elementos que perdieron directamente contra el ganador del torneo [47:55-48:11, 66:49-66:59].
5 Sitios o recursos para visitar
El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:
Árboles de decisión y por qué ordenar por comparaciones cuesta al menos log₂(n!). · google.com
Encontrar el mínimo y el segundo mínimo con la historia del torneo. · google.com
Demostración del límite inferior n log n para la ordenación por comparaciones. · geeksforgeeks.org
Libro de referencia clásico: ordenación, selección y límites inferiores. · google.com
Libro complementario de diseño y análisis de algoritmos. · google.com
6 Glosario de términos
- Árbol de decisiones: modelo de un algoritmo basado en comparaciones; cada nodo es una pregunta y cada hoja un resultado posible.
- Hoja: resultado final de un camino del árbol de decisiones.
- Altura del árbol (H): el número máximo de preguntas (comparaciones) a lo largo de un camino.
- Permutación: orden distinto de los n elementos; hay n! permutaciones.
- Límite inferior: cota mínima de costo que todo algoritmo debe cumplir, cualquiera sea su implementación.
- log₂(n!): altura mínima de un árbol de decisiones para ordenar n elementos por comparaciones.
- Mínimo: el elemento más pequeño de una lista; encontrarlo cuesta n−1 comparaciones.
- Método del torneo: comparar de a pares y hacer avanzar a los ganadores, como una eliminación directa.
- Historia del torneo: registro de las comparaciones realizadas; permite recuperar el segundo y tercer mínimo.
7 Mapa mental textual
- Diseño y Análisis de Algoritmos · Clase 3
- Árbol de decisiones
- Con H preguntas → como máximo 2^H hojas (1→2, 2→4, 3→8, 4→16)
- Cada comparación divide los casos en dos
- Límite inferior del ordenamiento
- Ordenar n elementos → n! permutaciones → n! hojas
- n = 3: 3! = 6 hojas → al menos 3 comparaciones (2 no alcanza)
- Altura del árbol = log₂(n!), no N
- Problema del mínimo
- Comparar desde el inicio, guardar el más pequeño y su posición
- Costo: n−1 comparaciones
- Método del torneo
- Comparar de a pares, avanzan los ganadores
- Segundo y tercer mínimo: entre los que perdieron directamente contra el ganador
- Árbol de decisiones